class DoublyLink:
    """双向链表，通常用来被其他类继承实现队列等"""

    # ---------------------双向链表---------------------
    class _Node:
        __slots__ = 'element', 'prev', 'next'

        def __init__(self, element, prev, next_):
            self.element = element
            self.prev = prev
            self.next = next_

    # ---------------------双向链表---------------------

    def __init__(self):
        self.header = self._Node(None, None, None)
        self.trailer = self._Node(None, self.header, None)
        self.header.next = self.trailer
        self.size = 0

    def len(self):
        return self.size

    def is_empty(self):
        return self.size == 0

    def insert_between(self, data, prev, next_):
        """在 prev和 next之间插入一个链表"""
        newest = self._Node(data, prev, next_)
        prev.next = newest
        next_.prev = newest
        self.size += 1
        return newest

    def del_node(self, node):
        """删除一个链表"""
        prev = node.prev
        next_ = node.next
        prev.next = next_
        next_.prev = prev
        self.size -= 1
        data = node.element
        node.prev = node.next = node.element = None
        return data

    def find_mid(self):
        """通过链接跳跃，找出中间节点的算法"""
        head = self.header.next
        tail = self.trailer.prev
        while True:
            if head.next == tail or head == tail:
                return head.element
            elif head.next == tail.prev:
                return head.next.element
            elif head.prev == tail:
                return tail.element
            else:
                head = head.next.next
                tail = tail.prev.prev

    def links(self,link):
        if not link.size:
            raise Exception('队列为空')
        first = link.header.next
        last = link.trailer.prev

        first.prev = self.trailer.prev
        last.next = self.trailer

        self.trailer.prev.next = first
        self.trailer.prev = last

        link.trailer.prev = None
        link.header.next = None
        
        self.size += link.size

    def __str__(self):
        data = ['head']
        current = self.header.next
        for i in range(self.size):
            data.append(current.element)
            current = current.next
        data.append('tail')
        return str(data)


class LinkedDeque(DoublyLink):
    """双向链表实现的双端队列"""

    def first(self):
        if self.is_empty():
            raise Exception('队列为空')
        return self.header.next.element

    def last(self):
        if self.is_empty():
            raise Exception('队列为空')
        return self.trailer.prev.element

    def insert_first(self, data):
        self.insert_between(data, self.header, self.header.next)

    def insert_last(self, data):
        self.insert_between(data, self.trailer, self.trailer.next)

    def del_first(self):
        """删除队首元素并返回"""
        if self.is_empty():
            raise Exception('队列为空')
        return self.del_node(self.header.next)

    def del_last(self):
        """删除队尾并返回"""
        if self.is_empty():
            raise Exception('队列为空')
        return self.del_node(self.trailer.prev)


if __name__ == '__main__':
    deque1 = LinkedDeque()
    deque2 = LinkedDeque()

    for i in range(10):
        deque1.insert_first(i)
        deque2.insert_first(10-i)

    print(deque1)
    print(deque2)
    deque1.links(deque2)
    print(deque1)
    print(deque1.last())
